package com.dmall.leetcode;

import java.util.*;

/**
 * LeetCode：347-Top K Frequent Elements
 * 使用java的工具类PriorityQueue
 * @author xiao1.wang@dmall.com
 * @date 2019-08-13 23:19:24
 */
public class Solution2 {

    private class Freq {
        public int e, freq;

        public Freq(int e, int freq) {
            this.e = e;
            this.freq = freq;
        }
    }

    private class FreqComparator implements Comparator<Freq> {

        @Override
        public int compare(Freq o1, Freq o2) {
            return o1.freq - o2.freq;
        }
    }

    public List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>(nums.length);
        for (int num : nums) {
            if (map.containsKey(num)) {
                map.put(num, map.get(num) + 1);
            } else {
                map.put(num, 1);
            }
        }

        PriorityQueue<Freq> queue = new PriorityQueue<>(map.keySet().size(), new FreqComparator());
        for (Integer num : map.keySet()) {
            if (queue.size() < k) {
                queue.add(new Freq(num, map.get(num)));
            } else {
                if (map.get(num) > queue.peek().freq) {
                    queue.remove();
                    queue.add(new Freq(num, map.get(num)));
                }
            }
        }

        List<Integer> list = new ArrayList<>(queue.size());
        while (!queue.isEmpty()) {
            list.add(queue.remove().e);
        }

        return list;
    }

    public static void main(String[] args) {
        int[] nums = {1, 1, 1, 2, 2, 3, 3, 3};
        int k = 2;
        System.out.println((new Solution2()).topKFrequent(nums, k));
    }
}
